package org.lql.algo.codecrush.week004;

import java.util.Stack;

/**
 * @author: liangqinglong
 * @date: 2025-08-01 17:42
 * @description: 面试题 03.05. 栈排序 <a href="https://leetcode.cn/problems/sort-of-stacks-lcci/description/">...</a>
 **/
public class SortedStack {

	/**
	 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。
	 * 最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
	 * 该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
	 * <p>
	 * 示例 1：
	 * <p>
	 * 输入：
	 * ["SortedStack", "push", "push", "peek", "pop", "peek"]
	 * [[], [1], [2], [], [], []]
	 * 输出：
	 * [null,null,null,1,null,2]
	 * 示例 2：
	 * <p>
	 * 输入：
	 * ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
	 * [[], [], [], [1], [], []]
	 * 输出：
	 * [null,null,null,null,null,true]
	 * 提示：
	 * <p>
	 * 栈中的元素数目在[0, 5000]范围内。
	 */

	private Stack<Integer> mainStack;
	private Stack<Integer> helperStack;

	public SortedStack() {
		mainStack = new Stack<>();
		helperStack = new Stack<>();
	}

	public void push(int val) {
		// Step 1: 把 mainStack 中比 val 小的放入 helperStack
		while (!mainStack.isEmpty() && mainStack.peek() < val) {
			helperStack.push(mainStack.pop());
		}

		// Step 2: 插入 val
		mainStack.push(val);

		// Step 3: 把 helperStack 中的元素移回 mainStack
		while (!helperStack.isEmpty()) {
			mainStack.push(helperStack.pop());
		}
	}

	public void pop() {
		if (!mainStack.isEmpty()) {
			mainStack.pop();
		}
	}

	public int peek() {
		return mainStack.isEmpty() ? -1 : mainStack.peek();
	}

	public boolean isEmpty() {
		return mainStack.isEmpty();
	}

	public static void main(String[] args) {
		SortedStack sortedStack = new SortedStack();
		sortedStack.push(1);
		sortedStack.push(2);
		sortedStack.push(3);
		sortedStack.push(4);
		sortedStack.push(5);
		sortedStack.pop();
		System.out.println(sortedStack.peek());
	}
}
